#include "main/utils.h"
using namespace std;

string alienOrder(const vector<string>& wordlist) {
  map<char, set<char>> graph;
  map<char, int> in_degrees;
  for (auto word : wordlist) {
    for (auto ch : word) {
      in_degrees[ch] = 0;
    }
  }

  for (int i = 1; i < wordlist.size(); ++i) {
    string w1 = wordlist[i - 1];
    string w2 = wordlist[i];
    if (w1.find(w2) == 0 && w2.compare(w1) != 0) {
      return "";
    }
    for (int j = 0; j < w1.size() && j < w2.size(); ++j) {
      if (w1[j] != w2[j]) {
        if (graph[w1[j]].find(w2[j]) == graph[w1[j]].end()) {
          graph[w1[j]].insert(w2[j]);
          in_degrees[w2[j]]++;
        }
        break;
      }
    }
  }

  queue<char> queue;
  for (auto ch : in_degrees) {
    if (ch.second == 0)
      queue.push(ch.first);
  }

  string ret;
  while (!queue.empty()) {
    auto cur = queue.front();
    queue.pop();
    ret.push_back(cur);
    for (auto next : graph[cur]) {
      --in_degrees[next];
      if (in_degrees[next] == 0) {
        queue.push(next);
      }
    }
  }
  return ret.size() == in_degrees.size() ? ret : "";
}

int main() {
  vector<string> wordlist = {"ac", "ab", "bc", "zc", "zb"};
  cout << alienOrder(wordlist) << endl;

  return 0;
}
